The present invention relates to switching technology in computer networks. More particularly it refers to a method and system for switching information packets through a multiple (m) input, multiple (n) output switching device.
During the last years the data traffic through electronic networks has increased remarkably. This tendency was strongly triggered by the general acceptance and frequent use of the Internet by private persons and enterprises.
In general, the data is transferred in packets from a start node to an end node of a respective data transmission. Between start node and end node in general, a plurality of nodes are used during packet transmission at which a packet is routed in one—when monocast—and into several directions—when multicast transmission—in order to arrive finally at the end node.
At any intermediate node a kind of switching device is provided having a number of m input ports and a number of n output ports that routes the packets according to the intended target node. The physical line onto which this is done is called a link. Thus, in a network the nodes are connected by one or more links which are often full duplex links which allow simultaneous communications in both directions. Both ends of each link are terminated by a ‘link-circuit’ which is also called a port.
A switch is thus a key component of the entire network. It is called non-blocking when it can simultaneously interconnect several pairs of selected links. It is also called a cut-through switch when it can begin re-transmitting (i.e., forwarding) data packets well before the complete packet has been received. Further, a modern switch supports multiple priorities or class of traffic per port, further referred to herein as lanes.
In European patent application EP 0404423 a respective disclosure can be found related to the specific prior art network switches. This disclosure is incorporated herein by reference.
The problem concerned with the present invention is now in more detail the following: The basic principle of any switch fabric is to route incoming packets from any of the m input ports to one or more of the n output ports.
The prior art disclosure M. Kateavenis, P. Vatsolaki, and A. Efthymiou, “Pipelined Memory Shared Buffer for VLSI Switches”, ACM SIGCOMM'95, MA USA, August 1995, pp.39-48, gives an overview on different ways of building a switch fabric by using various queuing systems such as Input Queuing (IQ), Output Queuing (OQ) or Combined Input and Output Queuing (CIOQ).
A switch fabric that places incoming packets in a queue that is dedicated to its outgoing line where it waits until departing of the switch, is called an output queued or output buffered switch fabric. This approach is considered to be the reference switch model as it provides the optimum delay-throughput performance for all traffic distributions. But this architecture is also considered to have limited scalability because the required internal bandwidth or speedup (S)—defined as the number of times that the switch core works faster than the input line rate—is equal to number of input ports (S=m). This makes output queuing impractical for switches with high line rates or with large number of ports, because memories with sufficient bandwidth are simply not available.
Therefore, most high performance switch (both research and commercial) have chosen architectures employing input queuing (also referred as input buffering) to reduce cost and simplify the implementation.
An input queued architecture is considered to be more scalable and its implementation does not have the restriction of an OQ model because the core fabric only needs to work at the input line rate (S=1). However, IQ based switches need to resolve input and output contention by means of arbiters at the inputs and outputs. Maximum matching algorithms have been proposed to achieve 100% throughput, but their high complexity make them unfeasible to implement for high-speed systems. These are schemes such as Longest Port Queuing (LPQ), Oldest Cell First (OCF) and Longest Port First (LPF). Maximal matching such as iSLIP, Dual Round-Robin Matching (DRRM) and Longest Output Occupancy First Alorithm (LOOFA) have been considered as an alternative to maximum matching schemes. These schemes are less complex to implement, but still because of the high requirements put on these arbiters, only switches with small number of ports (i.e 32 for iSLIP) have been proposed. Another drawback of IQ switches is that guaranteed Quality of Service (QoS) is usually difficult to implement. The reason is that packets not only contend for an output port, they also contend for entry into the switch fabric with packets that are destined for other outputs. This places a packet at the mercy of other packets destined for other outputs, and makes the packet latency difficult to control, unless a mechanism is provided to resolve input contention.
For a long time, buffered crossbars have been considered as the solution to improve switching throughput. A buffered crossbar has buffering at each crosspoint, meaning that incoming packets are queued per output at every inputs. This architecture takes advantage of the IQ implementation scalability by requiring a switch core that only operates at the input line rate (S=1), while also providing all the delay-throughput characteristics of an OQ switch.
From a queuing system point of view, a buffered crossbar can be seen as an output queued switch having distributed output queues instead of a centralized output queue. In order to behave identically to an OQ switch, a buffered crossbar requires an arbitration scheme between the physical distributed queues to recreate a logical output queue. (FIG. 1a). The conventional crosspoint-buffer-type switch adopts ring arbitration to search for a crosspoint buffer that has a request to send a packet to the output line. Because this scheme is known to be limited by the number of input ports and by the transmission delay of the control signals in each crosspoint, approaches such as Round-Robin (RR) or Weighted Round-Robin (WRR) arbitration are usually preferred.
However, even if their implementation is more scaleable, RR and WRR arbitration also experiment problems when both the input port increases to large numbers (i.e 128˜256) and the line rate increases in the range of tens of Gb/s. The reason is that packet time decreases as the input/output line rate increases, which puts a strong dependency on the high-speed logic that performs the arbitration decision within one packet cycle.
Also, although the RR and the WRR arbitration are suitable for many communication applications, their behavior may not be acceptable when the aim is to approximate or emulate a real output queued switch. In particular, some computer applications may require that the sequence of incoming packets among multiple input ports gets maintained. In those cases, more complex algorithms such as fair queuing type of algorithms are required, which again will limit the buffer crossbar scalability.